Căn bậc hai của 1 trong Z p {\displaystyle \mathbb {Z} _{p}}

Trước hết là một bổ đề về căn bậc hai của đơn vị trong trường hữu hạn Z p {\displaystyle \mathbb {Z} _{p}} , trong đó p là số nguyên tố. Chắc chắn rằng 1 và -1 luôn là các căn bậc hai của 1 theo module p. Chúng là hai căn bậc hai duy nhất của 1. Thật vậy, giả sử rằng x là một căn bậc hai của 1 theo module p. Khi đó:

x 2 ≡ 1 ( mod p ) {\displaystyle x^{2}\equiv 1{\pmod {p}}} x 2 − 1 ≡ 0 ( mod p ) {\displaystyle x^{2}-1\equiv 0{\pmod {p}}} ( x − 1 ) ( x + 1 ) ≡ 0 ( mod p ) {\displaystyle (x-1)(x+1)\equiv 0{\pmod {p}}}

Từ đó, x − 1 {\displaystyle x-1} hoặc x + 1 {\displaystyle x+1} là chia hết cho p.

Tiêu chuẩn Miller-Rabin

Bây giờ giả sử p là một số nguyên tố lẻ, khi đó p - 1 là số chẵn và ta có thể viết p − 1 dưới dạng 2 s ⋅ m {\displaystyle 2^{s}\cdot m} , trong đó s là một số tự nhiên >=1 và m là số lẻ - Điều này nghĩa là ta rút hết các thừa số 2 khỏi p − 1. Lấy số a bất kỳ trong tập { 1 ,   2 , … ,   p − 1 } {\displaystyle \{1,\ 2,\dots ,\ p-1\}} .

Xét dãy số x k = a 2 k . m {\displaystyle x_{k}=a^{2^{k}.m}} với k=0,1,2,...,s. Khi đó x k = ( x k − 1 ) 2 {\displaystyle x_{k}=(x_{k-1})^{2}} , với k=1,2,...,s và x s = a p − 1 {\displaystyle x_{s}=a^{p-1}}

Từ định lý Fermat nhỏ:

a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}}

hay

x s ≡ 1 ( mod p ) {\displaystyle x_{s}\equiv 1{\pmod {p}}}

hay

x s − 1 2 ≡ 1 ( mod p ) {\displaystyle {x_{s-1}}^{2}\equiv 1{\pmod {p}}} .

Do đó,hoặc x s − 1 ≡ 1 ( mod p ) {\displaystyle x_{s-1}\equiv 1{\pmod {p}}} hoặc x s − 1 ≡ − 1 ( mod p ) {\displaystyle x_{s-1}\equiv -1{\pmod {p}}} .
Nếu x s − 1 ≡ − 1 ( mod p ) {\displaystyle x_{s-1}\equiv -1{\pmod {p}}} ta dừng lại, còn nếu ngược lại ta tiếp tục với x s − 2 {\displaystyle x_{s-2}} .

Sau một số hữu hạn bước

• hoặc ta có một chỉ số k, 0 ≤ k ≤ s − 1 {\displaystyle 0\leq k\leq s-1} sao cho x k ≡ − 1 ( mod p ) {\displaystyle x_{k}\equiv -1{\pmod {p}}} ,
• hoặc tới k = 0 ta vẫn có x k ≡ 1 ( mod p ) {\displaystyle x_{k}\equiv 1{\pmod {p}}} .

Ta có mệnh đề Q(p, a) như sau:

Nếu p là số nguyên tố lẻ và p − 1 = 2 s ⋅ m {\displaystyle p-1=2^{s}\cdot m} thì ∀   a : 0 < a < p − 1 {\displaystyle \forall \ a:0<a<p-1} :

• hoặc x k = a 2 k ⋅ m ≡ 1 ( mod p ) ,   ∀   k = 0 ,   1 ,   2 , … ,   s {\displaystyle x_{k}=a^{2^{k}\cdot m}\equiv 1{\pmod {p}},\ \forall \ k=0,\ 1,\ 2,\dots ,\ s}
• hoặc tồn tại k: 0 ≤ k ≤ s {\displaystyle 0\leq k\leq s} sao cho x k = a 2 k ⋅ m ≡ − 1 ( mod p ) {\displaystyle x_{k}=a^{2^{k}\cdot m}\equiv -1{\pmod {p}}} .